\documentclass[submission]{FPSAC2017}

\articlenumber{69}
\addbibresource{69_Dwyer_Elizalde.bib}


\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{conj}{Conjecture}

\crefname{thm}{Theorem}{Theorems}

\usepackage{lipsum}
\usepackage{tikz}
\usepackage[normalem]{ulem}


\newcommand{\mfS}{\mathfrak{S}}
\newcommand{\mcO}{\mathcal{O}}
\newcommand{\mcL}{\mathcal{L}}
\newcommand{\st}{\operatorname{st}}
\newcommand{\emm}{\operatorname{em}}
\newcommand{\Em}{\operatorname{Em}}
\newcommand{\card}[1]{{\lvert #1 \rvert}} 	% cardinality


\title{A necessary condition for c-Wilf equivalence}

\author{Tim Dwyer \and Sergi Elizalde\thanks{
Partially supported by Simons Foundation grant \#280575 and NSA grant H98230-14-1-0125.}}


\address{Department of Mathematics, Dartmouth College, Hanover, NH, USA}

\received{\today}

\abstract{Two permutations $\pi$ and $\tau$ are {\em strongly c-Wilf equivalent} if, for each $n$ and~$k$, the number of permutations in $\mfS_n$ containing $k$ occurrences of $\pi$ as a consecutive pattern (i.e., in adjacent positions) is the same as for $\tau$. If the condition holds 
for any set of prescribed positions for the $k$ occurrences, we say that $\pi$ and $\tau$ are {\em super-strongly c-Wilf equivalent}, and if it holds for $k=0$, we say that $\pi$ and $\tau$ are {\em c-Wilf equivalent}.

We give a necessary condition for two permutations to be strongly c-Wilf equivalent. Specifically, we show that if \(\pi,\tau\in\mfS_m\)
are strongly c-Wilf equivalent, then \(|\pi_m-\pi_1|=|\tau_m-\tau_1|\). In the special case of non-overlapping permutations $\pi$ and $\tau$, 
this proves a weaker version of a conjecture of the second author stating that $\pi$ and $\tau$ are c-Wilf equivalent if and only if \(\pi_1=\tau_1\) and \(\pi_m=\tau_m\), up to trivial symmetries. 
Additionally, we show that for non-overlapping permutations, c-Wilf equivalence coincides with super-strong c-Wilf equivalence, and we strengthen a recent result of Nakamura and Khoroshkin--Shapiro giving sufficient conditions for strong c-Wilf equivalence.
}

\keywords{permutation, consecutive pattern, c-Wilf equivalence, poset}

\begin{document}

\maketitle

\section{Introduction and definitions}
The study of permutation patterns dates back at least to Knuth~\cite{Knuth1969}. The last three decades have seen an explosion of research in this area, and a number of questions have arisen involving different types of patterns in permutations, including \emph{consecutive, vincular, bivincular, mesh} and \emph{barred} patterns. A common question in all of these settings is, for a given pattern \(\pi\) of length \(m\), how many permutations \(\sigma\) of length \(n\) avoid this pattern. This is a very difficult question in general. Another related question is when two patterns have the same number of permutations of length \(n\) avoiding them, for all $n$. In the classical case, two patterns with this property are said to be Wilf equivalent. The classification of patterns into Wilf equivalence classes is a wide open problem. 

In this paper we focus on the analogous question for consecutive patterns, that is, patterns that occur in adjacent positions of the permutation. In this case, the notion analogous to Wilf equivalence is called {\em c-Wilf equivalence}, following the terminology from~\cite{NakamuraClusters}. Even though the classification of patterns into c-Wilf equivalence classes is also open, we are able to give a natural necessary condition in the case of non-overlapping patterns. We also investigate the related notions of strong and super-strong c-Wilf equivalence.

Consecutive patterns appear naturally when defining permutation statistics such as descents, peaks, valleys and runs, and also when defining alternating permutations. The systematic enumeration of permutations avoiding consecutive patterns started in~\cite{EN2003}, and it is now an active area of research (see the survey~\cite{Elizalde2016}). 

\medskip

Let \(\mfS_n\) be the symmetric group on \([n]\). For $\sigma\in\mfS_n$, we write $\sigma=\sigma_1\sigma_2\dots\sigma_n$ and let $|\sigma|=n$ denote its length.
Given two permutations \(\pi\in\mfS_m\) and \(\sigma\in\mfS_n\), we say that \(\sigma\) \emph{contains \(\pi\) as a consecutive pattern} if there is an \(i\in[n-m+1]\) for which \(\st(\sigma_{i}\dots\sigma_{i+m-1})=\pi\), where $\st$ is the {\em standardization} operation that 
replaces the smallest entry with a \(1\), the next smallest with a \(2\) and so on.
The substring $\sigma_{i}\dots\sigma_{i+m-1}$, identified by the position \(i\) where it begins, is called an \emph{occurrence} or an \emph{embedding} of \(\pi\) in~\(\sigma\). For example the permutation \(\sigma=43815672\) contains the pattern \(51234\) at position \(3\), since $\st(81567)=51234$.  Define \(\Em(\pi,\sigma)\) to be the set of occurrences (more specifically, the set of positions where these occurrences begin) of \(\pi\) in \(\sigma\), and let \(\card{\Em(\pi,\sigma)}=\emm(\pi,\sigma)\). For example $\Em(21,345261)=\{3,5\}$ and $ \emm(21,345261)=2$ are just the descent set and descent number of \(345261\).

To count occurrences of a consecutive pattern $\pi$ in permutations, we use the exponential generating function
$$P_\pi(u,z)=\sum_{\sigma}\frac{z^{|\sigma|}}{|\sigma|!}u^{em(\pi,\sigma)},$$
where the sum is taken of all permutations \(\sigma\in\bigcup_{n\ge0}\mfS_n\). The coefficient of \(z^n u^k\) in \(P_\pi(u,z)\) is \({a_{n,k}^\pi}/{n!}\), where \(a_{n,k}^\pi\) is the number of permutations \(\sigma\in\mfS_n\) with \(\emm(\pi,\sigma)=k\). For a few specific patterns $\pi$, an explicit formula is known for this generating function.
For example, it was shown by Elizalde and Noy \cite{EN2003} that, for $\pi\in\mfS_m$ with $\pi_1=1$, $\pi_m=2$ and $m\ge3$,
$$
P_{\pi}(u,z)=\frac{1}{1-\int_{0}^{z} e^{\frac{(u-1)t^{m-1}}{(m-1)!}}dt}.
$$
However, finding expressions for $P_{\pi}(u,z)$ in general is a difficult problem.

Instead, in this extended abstract we focus on some natural equivalence relations that arise from the definition of consecutive patterns. Two permutations $\pi$ and $\tau$ are called \emph{strongly c-Wilf equivalent} if \(P_\pi(u,z)=P_\tau(u,z)\), and they are called \emph{c-Wilf equivalent} if \(P_\pi(0,z)=P_\tau(0,z)\). Note that \(P_\pi(0,z)\) is the generating function for permutations which avoid \(\pi\). It was conjectured by Nakamura~\cite{NakamuraClusters} that these relations are actually the same:

\begin{conj}[{\cite[Conjecture 5.6]{NakamuraClusters}}]\label{conj:Nak} For permutations $\pi$ and $\tau$, we have
 \(P_\pi(u,z)=P_\tau(u,z)\) if and only if \(P_\pi(0,z)=P_\tau(0,z)\).
\end{conj}

For \(\pi\in\mfS_m\), its \emph{overlap set} \(\mcO_\pi\) is the set of indices \(i\in[m-1]\) such that \(\st(\pi_{i+1}\cdots \pi_{m})=\st(\pi_1\cdots\pi_{m-i})\). The overlap set keeps track of which suffixes and prefixes of \(\pi\) have the same standardization. Note that we always have $m-1\in\mcO_\pi$. The \emph{non-overlapping} permutations are those for which \(\mcO_\pi=\{m-1\}\). \cref{conj:Nak} was proved in \cite{ElizaldeNoyClusters2012} in the special case of non-overlapping  permutations. 

There is a nice sufficient condition for strong c-Wilf equivalence of two permutations with the same overlap set, proved independently by
Nakamura \cite{NakamuraClusters} and Khoroshkin and Shapiro  \cite{khoshap}:
\begin{thm}[\cite{NakamuraClusters,khoshap}]\label{thm:KS}
If \(\pi,\tau\in\mfS_m\) with \(\mcO_\pi=\mcO_\tau\) satisfy \(\{\pi_1,\dots,\pi_{m-i}\}=\{\tau_1,\dots,\tau_{m-i}\}\) and \(\{\pi_{i+1}\dots,\pi_m\}=\{\tau_{i+1},\dots,\tau_m\}\) for all \(i\in\mcO_\pi\), then $\pi$ and $\tau$ are strongly c-Wilf equivalent. 
\end{thm}


For the case of non-overlapping permutations, \cref{thm:KS} simply says that if \(\pi_1=\tau_1\) and \(\pi_m=\tau_m\), then 
 $\pi$ and $\tau$ are strongly c-Wilf equivalent. This fact had been already shown in~\cite{DotKho2013,DR2011,ElizaldeMostLeast2013}.
It was conjectured in \cite{ElizaldeMostLeast2013} that, for non-overlapping patterns, this condition completely characterizes c-Wilf equivalence. To be precise, first we note that every permutation \(\tau\in\mfS_m\) is c-Wilf equivalent to its reversal, complement and reverse-complement, defined as \(\tau^R=\tau_m\cdots\tau_1\), \(\tau^C=(m+1-\tau_1)\cdots (m+1-\tau_m)\) and \(\tau^{RC}=(m+1-\tau_m)\cdots(m+1-\tau_1)\), respectively. It is easy to see that there is precisely one permutation $\pi\in\{\tau,\tau^R,\tau^C,\tau^{RC}\}$ satisfying \(\pi_1<\pi_m\) and \(\pi_1+\pi_m\le m+1\). Such a \(\pi\) is said to be in \emph{standard form}. Now we can formulate the conjecture precisely. We state it as a necessary condition, since it is already known to be sufficient.

\begin{conj}[\cite{ElizaldeMostLeast2013}]
\label{elizaldeconj}
Let \(\pi,\tau\in\mfS_m\) be non-overlapping and in standard form. If they are c-Wilf equivalent, then \(\pi_1=\tau_1\) and \(\pi_m=\tau_m\).
\end{conj}

Even though \cref{elizaldeconj} applies only to non-overlapping patterns, we can formulate a related conjecture without this restriction. As mentioned above, for non-overlapping patterns, c-Wilf equivalence is the same as strong c-Wilf equivalence, so the following conjecture includes \cref{elizaldeconj} as a special case.

\begin{conj}
\label{dwyerconj}
Let \(\pi,\tau\in\mfS_m\) be in standard form. If they are strongly c-Wilf equivalent, then \(\pi_1=\tau_1\) and \(\pi_m=\tau_m\).
\end{conj}

We prove in \cref{clustersec} that if the conjecture about non-overlapping patterns holds, then so does the general conjecture:

\begin{thm}
\label{thm1}
\cref{elizaldeconj} implies \cref{dwyerconj}.
\end{thm}

One of our main results, which we also prove in \cref{posetsec}, is the following weaker version of \cref{dwyerconj}:
\begin{thm}
\label{thm2}
Let \(\pi,\tau\in\mfS_m\) be in standard form. If they are strongly c-Wilf equivalent, then \(\pi_m-\pi_1=\tau_m-\tau_1\).
\end{thm}

In \cref{superstrong} we define a third equivalence relation on permutations that refines strong c-Wilf equivalence.
Define \(a_{n,S}^\pi\) to be the number of permutations \(\sigma\in\mfS_n\) with \(\Em(\pi,\sigma)=S\). Two permutations \(\pi,\tau\in\mfS_m\) are called \emph{super-strongly c-Wilf equivalent} if \(a_{n,S}^\pi=a_{n,S}^\tau\) for all \(n\) and \(S\). Our \cref{thm:DE-ss} generalizes \cref{thm:KS} to super-strong equivalence. It is obtained by first extending the ideas from cluster method in order to keep track of not only of the number of occurrences but also of their positions, as stated in \cref{lem:Cluster-ss}. Finally, in \cref{thm:eq-sseq} we show that, for non-overlapping patterns, c-Wilf equivalence implies super-strong c-Wilf equivalence.


\section{The cluster method}
The cluster method was introduced in the context of words by Goulden and Jackson \cite{ClusterOriginal} to give a a combinatorial interpretation of the reciprocal of the generating function of words over an alphabet refined by occurrences of specific substrings. Nakamura \cite{NakamuraClusters} adapted it to consecutive permutation patterns. Given a pattern $\pi$, rather than counting permutations \(\sigma\) with \(\emm(\pi,\sigma)=k\), one counts ordered pairs \((\sigma,S)\) with \(|S|=k\) and \(S\subseteq\Em(\pi,\sigma)\). We call such an ordered pair a a \emph{marked permutation}, since the occurrences of $\pi$ in positions in $S$ are marked. We represent marked occurrences by underlining them in \(\sigma\). For example, for $\pi=321$, the marked permutation \((432179865,\{1,2,7\})\) can be represented as \(\underline{4\underline{32}}\underline{1}79\underline{865}\). 

The cluster method expresses \(P_{\pi}(u,z)\) in terms of the generating function for a special type of marked permutations called \emph{clusters}. Given \(\pi\in\mfS_m\), a marked permutation \((\sigma,S)\) is a \(\pi\)-cluster if $\sigma\in\mfS_n$, and \(S=\{i_1<\cdots<i_k\}\subseteq\Em(\pi,\sigma)\) satisfies the following conditions:
\begin{itemize}
\item \(1, n-m+1\in S\),
\item \(i_{j+1}-i_j\in\mcO_\pi\) for all \(j\in[k-1]\).
\end{itemize}
In other words, both $\sigma_1$ and $\sigma_n$ belong to a marked occurrence, and each marked occurrence overlaps the next one.
The previous example of a marked permutation is not a \(321\)-cluster, but both \(\uline{4\uline{32}}\uline{1}\) and \(\uline{54\uline{3}}\uline{21}\) are. 
Define the cluster generating function
$$R_\pi(u,z)=\sum_{(\sigma,S)}\frac{z^{|\sigma|}}{|\sigma|!}u^{|S|},$$
where the sum is taken over all \(\pi\)-clusters \((\sigma,S)\). The coefficient of \(z^n u^k\) in \(R_\pi(u,z)\) is \(r_{n,k}^\pi/n!\), where \(r_{n,k}^\pi\) is the number of \(\pi\)-clusters \((\sigma,S)\) where  \(\sigma\in\mfS_n\) and \(|S|=k\). The numbers \(r_{n,k}^\pi\) are called the \emph{cluster numbers} of \(\pi\). 

A marked permutation can be identified with a sequence consisting of unmarked entries interspersed with strings of overlapping marked occurrences that would be clusters if the underlying word was standardized. For example, the marked permutation \(\underline{4\underline{32}}\underline{1}79\underline{865}\) corresponds to the sequence  \((\underline{4\underline{32}}\underline{1},7,9,\underline{865})\). This identification provides the desired connection between our generating functions. 

\begin{thm}[\cite{ClusterOriginal,NakamuraClusters}]
\label{clustermethod}
For any permutation \(\pi\), we have
$$P_\pi(u,z)=\frac{1}{1-z-R_\pi(u-1,z)}.$$
\end{thm}
It follows immediately that \(P_\pi(u,z)=P_\tau(u,z)\) if and only if \(r_{n,k}^\pi=r_{n,k}^\tau\) for all \(n\) and \(k\).


\subsection{Cluster posets}
Elizalde and Noy \cite{ElizaldeNoyClusters2012} established a connection between cluster numbers and linear extensions of posets. Fix \(\pi\in\mfS_m\). We can write $$r_{n,k}^\pi=\sum_{S} \sum_{\sigma}1,$$
where the exterior sum is taken over all sets \(S\subseteq[n-m+1]\) with $|S|=k$ satisfying the two conditions in the definition of a cluster, and the interior sum is over all \(\sigma\in\mfS_n\) for which \(S\subseteq\Em(\pi,\sigma)\). The value of the interior sum is denoted  by \(r_{n,S}^\pi\) and called a \emph{refined cluster number}. We can now write \(r_{n,k}^\pi=\sum_{S}r_{n,S}^\pi\).

For each $n$ and $S$ as above, we define a poset \(P_{n,S}^\pi\) on the set \(\{\sigma_1,\ldots,\sigma_n\}\) generated by the order relationships forced by the fact that $\sigma_1\dots\sigma_n$ must have occurrences of $\pi$ at each $i\in S$.
We call \(P_{n,S}^\pi\) a \emph{cluster poset}, and we note that, by definition, it has exactly \(r_{n,S}^\pi\) linear extensions. By way of example, suppose that \(\pi=513624\), \(S=\{1,4,7\}\) and $n=12$. Then \(r_{12,S}^\pi\) is the number of permutations \(\sigma\in\mfS_{12}\) satisfying
\begin{align}
\label{example1}
\st(\sigma_1\sigma_2\sigma_3\sigma_4\sigma_5\sigma_6)=\st(\sigma_4\sigma_5\sigma_6\sigma_7\sigma_8\sigma_9)=\st(\sigma_7\sigma_8\sigma_9\sigma_{10}\sigma_{11}\sigma_{12})=513624.
\end{align}
Noting that \(\pi^{-1}=253614\), Equation \eqref{example1} is equivalent to the following 3 chains of inequalities:
\begin{align*}
&\sigma_{2}<\sigma_{5}<\sigma_{3}<\sigma_{6}<\sigma_{1}<\sigma_{4},\\
&\sigma_{5}<\sigma_{8}<\sigma_{6}<\sigma_{9}<\sigma_{4}<\sigma_{7},\\
&\sigma_{8}<\sigma_{11}<\sigma_{9}<\sigma_{12}<\sigma_{7}<\sigma_{10}.
\end{align*}
The cluster poset \(P_{12,S}^{\pi}\) is defined by the transitive closure of these relations, and its Hasse diagram is given in \cref{fig1}. Note that this poset is well-defined because all the symbols which appear in multiple chains have the same ordering in each chain. 

\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=1.2]
    \draw [thick] (0,0) -- (0,3.5);
    \draw[black,fill=black] (0,0) circle (.25ex);
    \draw[black,fill=black] (0,.5) circle (.25ex);
    \draw[black,fill=black] (0,1) circle (.25ex);
    \draw[black,fill=black] (0,1.5) circle (.25ex);
    \draw[black,fill=black] (0,2) circle (.25ex);
    \draw[black,fill=black] (0,2.5) circle (.25ex);
    \draw[black,fill=black] (0,3) circle (.25ex);
    \draw[black,fill=black] (0,3.5) circle (.25ex);
    
    
    \draw[black,fill=black] (.5,1) circle (.25ex);
    \draw[black,fill=black] (.5,2) circle (.25ex);
    \draw[black,fill=black] (1,1.5) circle (.25ex);
    \draw[black,fill=black] (.75,2.5) circle (.25ex);

    
    
    \draw [thick] (0,0.5) -- (.5,1);
    \draw [thick] (0.5,1) -- (0,1.5);
    
    \draw [thick] (0,1.5) -- (0.5,2) -- (0.75,2.5);
    \draw [thick] (0.5,2) -- (0,2.5);
    \draw [thick] (0,3) -- (.75,2.5);

    
    \draw [thick] (.5,1) -- (1,1.5);
    \draw [thick] (1,1.5) -- (.5,2);

  
 \node at (-.25,0) {\(\sigma_2\)};
 \node at (-.25,.5) {\(\sigma_5\)};
 \node at (-.25,1) {\(\sigma_3\)};
 \node at (-.25,1.5) {\(\sigma_6\)};
 \node at (-.25,2) {\(\sigma_1\)};
 \node at (-.25,2.5) {\(\sigma_4\)};
 \node at (-.25,3) {\(\sigma_7\)};
 \node at (-.4,3.5) {\(\sigma_{10}\)};

 \node at (.5,.75) {\(\sigma_{8}\)};
 \node at (.5,1.75) {\(\sigma_{9}\)};
 \node at (1.2,1.25) {\(\sigma_{11}\)};
 \node at (1.1,2.5) {\(\sigma_{12}\)};
\end{tikzpicture}
\caption{The Hasse diagram of \(P_{12,\{1,4,7\}}^{513624}\).}
\label{fig1}
\end{figure}

For the explicit definition of \(P_{n,S}^\pi\) in general, define \(\eta=\pi^{-1}\) and take the transitive closure of the \(k\) chains of inequalities on the set \(\{\sigma_1,\ldots, \sigma_n\}\) obtained for each \(i\in S\):
\begin{align*}
\sigma_{i-1+\eta_1}<\sigma_{i-1+\eta_2}<\cdots<\sigma_{i-1+\eta_m}.
\end{align*}


\subsection{Posets for non-overlapping permutations}
\label{ss:posetstructure}
The cluster posets of non-overlapping permutations have a particularly simple structure. First, note that if \(\pi\in\mfS_m\) is non-overlapping, then \(r_{n,k}^\pi=0\) unless \(n=1+k(m-1)\). This is because in order to have $k$ occurrences of \(\pi\) form a cluster, each one must overlap the next one on exactly one letter, and so each occurrence of \(\pi\) after the first adds \(m-1\) new letters. Additionally, 
\(r_{n,S}^\pi=0\) unless \(S=\{1,m,\ldots, 1+ (k-1)(m-1)\}\), where \(n=1+k(m-1)\). We denote this set by \(S(k,m)\). 
This second fact is actually true for every \(\pi\in\mfS_m\), regardless of whether or not it is non-overlapping: if $|S|=k$, then \(r_{1+k(m-1),S}^\pi=0\) unless \(S=S(k,m)\).

Suppose that \(\pi\in\mfS_m\) is in standard form and that \(\pi_1=a\) and \(\pi_m=b\). Then the poset \(P_{1+k(m-1),S(k,m)}^\pi\) consists of one long chain \(C\) with \(b+(k-2)(b-a)+m-a\) nodes, 
 together with \(k-1\) additional chains \(D_1,\ldots, D_{k-1}\) with \(m-b+a\) nodes. The chains $D_i$ are disjoint, and each of them intersects $C$ at one node, which is the \(a\)-th smallest element of \(D_i\) and the \((b+(i-1)(b-a))\)-th smallest element of \(D\). 
The Hasse diagrams of the posets $P^\pi_{22,\{1,8,15\}}$, $P^\pi_{29,\{1,8,15,22\}}$, $P^\pi_{36,\{1,8,15,22,29\}}$ for \(\pi=34671285\) are shown in \cref{fig2}. A more general drawing of the Hasse diagram of \(P_{4,S(4,m)}^\pi\) for arbitrary \(\pi\in\mfS_m\) in standard form is given in \cref{fig3}, where the \(k-1\) chains \(D_1,\ldots,D_{k-1}\) are drawn diagonally and the chain \(C\) is drawn vertically.
It follows from the above description that \(P_{1+k(m-1),S(k,m)}^\pi\) depends only on $\pi_1$ and $\pi_m$, a key fact in the proof of \cref{thm1}. Additionally,  this description of the cluster posets \(P_{1+k(m-1),S(k,m)}^\pi\) will be useful when proving \cref{lemma} and then \cref{thm2} in the next section.



\begin{figure}[htb]
\centering
%k=3
\begin{tikzpicture}[scale=.4]
    \draw [thick] (0,-1) -- (0,10);
    \draw[black,fill=black] (0,-1) circle (.7ex);
    \draw[black,fill=black] (0,0) circle (.7ex);
    \draw[black,fill=black] (0,1) circle (.7ex);
    \draw[black,fill=black] (0,2) circle (.7ex);
    \draw[black,fill=black] (0,3) circle (.7ex);
    \draw[black,fill=black] (0,4) circle (.7ex);
    \draw[black,fill=black] (0,5) circle (.7ex);
    \draw[black,fill=black] (0,6) circle (.7ex);
    \draw[black,fill=black] (0,7) circle (.7ex);
    \draw[black,fill=black] (0,8) circle (.7ex);
    \draw[black,fill=black] (0,9) circle (.7ex);
    \draw[black,fill=black] (0,10) circle (.7ex);



    \draw [thick] (-3,6) -- (2,1);
    \draw[black,fill=black] (-3,6) circle (.7ex);
    \draw[black,fill=black] (-2,5) circle (.7ex);
    \draw[black,fill=black] (-1,4) circle (.7ex);
    \draw[black,fill=black] (0,3) circle (.7ex);
    \draw[black,fill=black] (1,2) circle (.7ex);
    \draw[black,fill=black] (2,1) circle (.7ex);


    \draw [thick] (-3,8) -- (2,3);
    \draw[black,fill=black] (-3,8) circle (.7ex);
    \draw[black,fill=black] (-2,7) circle (.7ex);
    \draw[black,fill=black] (-1,6) circle (.7ex);
    \draw[black,fill=black] (0,5) circle (.7ex);
    \draw[black,fill=black] (1,4) circle (.7ex);
    \draw[black,fill=black] (2,3) circle (.7ex);
    \node at (0,-2.5) {\(P^{\pi}_{22,\{1,8,15\}}\)};



%k=4
  \draw [thick] (6,-1) -- (6,12);
    \draw[black,fill=black] (6,-1) circle (.7ex);
    \draw[black,fill=black] (6,0) circle (.7ex);
    \draw[black,fill=black] (6,1) circle (.7ex);
    \draw[black,fill=black] (6,2) circle (.7ex);
    \draw[black,fill=black] (6,3) circle (.7ex);
    \draw[black,fill=black] (6,4) circle (.7ex);
    \draw[black,fill=black] (6,5) circle (.7ex);
    \draw[black,fill=black] (6,6) circle (.7ex);
    \draw[black,fill=black] (6,7) circle (.7ex);
    \draw[black,fill=black] (6,8) circle (.7ex);
    \draw[black,fill=black] (6,9) circle (.7ex);
    \draw[black,fill=black] (6,10) circle (.7ex);
    \draw[black,fill=black] (6,11) circle (.7ex);
    \draw[black,fill=black] (6,12) circle (.7ex);



    \draw [thick] (3,6) -- (8,1);
    \draw[black,fill=black] (3,6) circle (.7ex);
    \draw[black,fill=black] (4,5) circle (.7ex);
    \draw[black,fill=black] (5,4) circle (.7ex);
    \draw[black,fill=black] (6,3) circle (.7ex);
    \draw[black,fill=black] (7,2) circle (.7ex);
    \draw[black,fill=black] (8,1) circle (.7ex);


    \draw [thick] (3,8) -- (8,3);
    \draw[black,fill=black] (3,8) circle (.7ex);
    \draw[black,fill=black] (4,7) circle (.7ex);
    \draw[black,fill=black] (5,6) circle (.7ex);
    \draw[black,fill=black] (6,5) circle (.7ex);
    \draw[black,fill=black] (7,4) circle (.7ex);
    \draw[black,fill=black] (8,3) circle (.7ex);


    \draw [thick] (3,10) -- (8,5);
    \draw[black,fill=black] (3,10) circle (.7ex);
    \draw[black,fill=black] (4,9) circle (.7ex);
    \draw[black,fill=black] (5,8) circle (.7ex);
    \draw[black,fill=black] (6,7) circle (.7ex);
    \draw[black,fill=black] (7,6) circle (.7ex);
    \draw[black,fill=black] (8,5) circle (.7ex);
    \node at (6,-2.5) {\(P^{\pi}_{29,\{1,8,15,22\}}\)};



%k=5
  \draw [thick] (13,-1) -- (13,14);
    \draw[black,fill=black] (13,-1) circle (.7ex);
    \draw[black,fill=black] (13,0) circle (.7ex);
    \draw[black,fill=black] (13,1) circle (.7ex);
    \draw[black,fill=black] (13,2) circle (.7ex);
    \draw[black,fill=black] (13,3) circle (.7ex);
    \draw[black,fill=black] (13,4) circle (.7ex);
    \draw[black,fill=black] (13,5) circle (.7ex);
    \draw[black,fill=black] (13,6) circle (.7ex);
    \draw[black,fill=black] (13,7) circle (.7ex);
    \draw[black,fill=black] (13,8) circle (.7ex);
    \draw[black,fill=black] (13,9) circle (.7ex);
    \draw[black,fill=black] (13,10) circle (.7ex);
    \draw[black,fill=black] (13,11) circle (.7ex);
    \draw[black,fill=black] (13,12) circle (.7ex);
    \draw[black,fill=black] (13,13) circle (.7ex);
    \draw[black,fill=black] (13,14) circle (.7ex);



    \draw [thick] (10,6) -- (15,1);
    \draw[black,fill=black] (10,6) circle (.7ex);
    \draw[black,fill=black] (11,5) circle (.7ex);
    \draw[black,fill=black] (12,4) circle (.7ex);
    \draw[black,fill=black] (13,3) circle (.7ex);
    \draw[black,fill=black] (14,2) circle (.7ex);
    \draw[black,fill=black] (15,1) circle (.7ex);


    \draw [thick] (10,8) -- (15,3);
    \draw[black,fill=black] (10,8) circle (.7ex);
    \draw[black,fill=black] (11,7) circle (.7ex);
    \draw[black,fill=black] (12,6) circle (.7ex);
    \draw[black,fill=black] (13,5) circle (.7ex);
    \draw[black,fill=black] (14,4) circle (.7ex);
    \draw[black,fill=black] (15,3) circle (.7ex);


    \draw [thick] (10,10) -- (15,5);
    \draw[black,fill=black] (10,10) circle (.7ex);
    \draw[black,fill=black] (11,9) circle (.7ex);
    \draw[black,fill=black] (12,8) circle (.7ex);
    \draw[black,fill=black] (13,7) circle (.7ex);
    \draw[black,fill=black] (14,6) circle (.7ex);
    \draw[black,fill=black] (15,5) circle (.7ex);


    \draw [thick] (10,12) -- (15,7);
    \draw[black,fill=black] (10,12) circle (.7ex);
    \draw[black,fill=black] (11,11) circle (.7ex);
    \draw[black,fill=black] (12,10) circle (.7ex);
    \draw[black,fill=black] (13,9) circle (.7ex);
    \draw[black,fill=black] (14,8) circle (.7ex);
    \draw[black,fill=black] (15,7) circle (.7ex);
    \node at (13,-2.5) {\(P^{\pi}_{36,\{1,8,15,22,29\}}\)};
\end{tikzpicture}
\caption{Some cluster posets for the non-overlapping permutation $\pi=34671285$.}
\label{fig2}
\end{figure}
 

\begin{figure}[htb]
\centering
%k=3
\begin{tikzpicture}[scale=.4]
    \draw [thick] (0,2) -- (0,4.25);
    \draw [thick] (0,6.25)--(0,8.75);
    \draw [thick] (0,10.75) -- (0,14);
    \draw[black,fill=black] (0,3) circle (.7ex);
    \draw[black,fill=black] (0,7.5) circle (.7ex);
    \draw[black,fill=black] (0,12) circle (.7ex);


    \draw [thick] (-1,4) -- (1,2);
    \draw [thick] (-1,8.5) -- (1,6.5);
    \draw [thick] (-1,13) -- (1,11);
%rotate around={45:(4,-1)}
    %lower arms
\draw[rotate around={45:(1,2)},shift={(.75,0)}, fill=red ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[rotate around={45:(1,6.5)},shift={(.75,4.5)}, fill=red] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[rotate around={45:(1,11)},shift={(.75,9)}, fill=red ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (4,1) {\(a-1\)};
\node at (4,5.5) {\(a-1\)};
\node at (4,10) {\(a-1\)};

    %upper arms
\draw[rotate around={225:(-1,4)},shift={(-1.25,1)}, fill=blue] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[rotate around={225:(-1,8.5)},shift={(-1.25,5.5)}, fill=blue] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[rotate around={225:(-1,13)},shift={(-1.25,10)}, fill=blue ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\node at (-4.25,5) {\(m-b\)};
\node at (-4.25,9.5) {\(m-b\)};
\node at (-4.25,14) {\(m-b\)};



%middle chain
\draw[shift={(-.25,4.25)}, fill=green] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[shift={(-.25,8.75)}, fill=green] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (2.5,3.75) {\(b-a-1\)};
\node at (2.5,8.25) {\(b-a-1\)};

%top chain
\draw[shift={(-.25,14)}, fill=yellow] (0,0) -- (.5,0) -- (.5,4) -- (0,4) -- (0,0);
\node at (2,16) {\(m-a\)};

%bottom chain
\draw[shift={(-.25,-1.5)}, fill=brown] (0,0) -- (.5,0) -- (.5,3.5) -- (0,3.5) -- (0,0);
\node at (-1.75,0) {\(b-1\)};

\end{tikzpicture}
\caption{The cluster poset \(P_{1+4(m-1),S(4,m)}^\pi\) of a permutation \(\pi\in\mfS_m\) in standard form with \(\pi_1=a\) and \(\pi_m=b\).}
\label{fig3}
\end{figure}


\section{Proofs of \cref{thm1,thm2}}
\label{clustersec}\label{posetsec}

Having characterized cluster posets for non-overlapping permutations, we are now able to prove \cref{thm1}.

\begin{proof}[Proof of \cref{thm1}]
It is easy to check that \cref{dwyerconj} holds for \(m\le 4\). Indeed, for $m=3$ there are only two permutations in standard form, namely $123$ and $132$, and they are not c-Wilf equivalent. For $m=4$, there are \(8\) permutations in \(\mfS_4\) in standard form, namely $1234$, $1243$, $1324$, $1342$, $1423$, $1432$, $2143$, and $2413$, and the only two that are c-Wilf equivalent are \(1342\) and \(1432\) \cite{EN2003}, which have the same first and last letter. 

Now suppose that \(m\ge5\) and \(\pi,\tau\in\mfS_m\) are in standard form and strongly c-Wilf equivalent. By \cref{clustermethod}, we know that \(r_{n,k}^\pi=r_{n,k}^\tau\) for all \(n\) and \(k\). In particular, taking \(n=1+k(m-1)\), we have \(r_{1+k(m-1),k}^\pi=r_{1+k(m-1),k}^\tau\) for all \(k\). If \(\pi_m=m\), then the condition  \(\pi_1+\pi_m\le m+1\) forces \(\pi_1=1\), and so \(r_{1+k(m-1),k}^\pi=1=r_{1+k(m-1),k}^\tau\) for all \(k\ge1\). But this can only happen if \(P_{1+k(m-1),S(k,m)}^\tau\) is a chain, which forces \(\tau_1=1\) and \(\tau_m=m\) as well. A symmetric argument shows that if $\tau_m=m$, then $\pi_1=\tau_1=1$ and $\pi_m=\tau_m=m$. 
 
We are left with the case \(\pi_m, \tau_m<m\). 
 In this case, we construct two non-overlapping permutations \(p,t\in\mfS_m\) with the same first and last letters as \(\pi\) and \(\tau\), respectively, following a construction from~\cite{ElizaldeMostLeast2013}:
\begin{align*}
p&=\pi_1(\pi_1+1)\dots(\pi_m-1)(\pi_m+1)\dots(m-1)12\dots(\pi_1-1)m\pi_m,\\
t&=\tau_1(\tau_1+1)\dots(\tau_m-1)(\tau_m+1)\dots(m-1)12\dots(\tau_1-1)m\tau_m.
\end{align*}
As discussed in \cref{ss:posetstructure}, the poset \(P_{1+k(m-1),S(k,m)}^\pi\) depends only on $\pi_1$ and $\pi_m$. It follows that  \(r_{1+k(m-1),k}^\pi=r_{1+k(m-1),k}^p\) and \(r_{1+k(m-1),k}^\tau=r_{1+k(m-1),k}^t\) for all \(k\). Since \(p\) and \(t\) are non-overlapping, these are their only non-zero cluster numbers, and so $p$ and $t$ are c-Wilf equivalent. Now \cref{elizaldeconj} states that \(p\) and \(t\) must have the same first and last letter, and thus the same holds for \(\pi\) and \(\tau\), implying \cref{dwyerconj}. \end{proof}

\medskip

Next we focus our attention on \cref{thm2}. The proof is based on the following result,
which allows us to extract information about the quantity \(\pi_m-\pi_1\) from the sequence \(r_{1+k(m-1),S(k,m)}^\pi\).

\begin{lem}
\label{lemma}
Let \(\pi\in\mfS_m\) be in standard form. Then there exist positive constants \(L_\pi,U_\pi\) and $K$ such that for all $k\ge K$,
$$ L_\pi\, k^{m-\pi_m+\pi_1-1}\le \left(r_{1+k(m-1),k}^\pi\right)^{1/k}\le U_\pi\, k^{m-\pi_m+\pi_1-1}. $$
\end{lem}

\begin{proof}
First we note that if we have two posets \(R\) and \(Q\) on the same set \(X\) with order relations \(\le_R\) and \(\le_Q\) such that $x\le_R y$ implies $x\le_Q y$ for all \(x,y\in X\), then \(R\) has at least as many linear extensions as \(Q\). We obtain upper and lower bounds for \(r_{1+k(m-1),S(k,m)}^\pi\) by removing and adding relations to \(P_{1+k(m-1),S(k,m)}^\pi\) and counting the number of linear extensions of the resulting modified posets. We use the same notation introduced in the second paragraph of \cref{ss:posetstructure} throughout the proof and recall that \(r_{1+k(m-1),k}^\pi=r_{1+k(m-1),S(k,m)}^\pi\). 
 It is helpful to refer to \cref{fig3} and to think of the constructions of the posets below as adding (or removing) relations between the rectangles themselves.

We will build two new posets $U_k^\pi$ and $L_k^\pi$ with $\ell_k^\pi$ and $u_k^\pi$ linear extensions, respectively, such that \(\ell_k^\pi\le r_{1+k(m-1),S(k,m)}^\pi\le u_{k}^\pi\). Then we will show that, as \(k\to\infty\), \(\left(\ell_k^\pi\right)^{q/k}\sim N k^{m-b+a-1}\) and \(\left(u_k^\pi\right)^{1/k}\sim Mk^{m-b+a-1}\)  for some positive constants \(N\) and \(M\). It follows that the sequence \(\frac{\left(r_{1+k(m-1),k}^\pi\right)^{1/k}}{k^{m-b+a-1}}\) is bounded away from \(0\) and \(\infty\) as \(k\to\infty\), which is equivalent to the existence of \(L_\pi\), \(U_\pi\) and $K$.

\medskip

\noindent {\sl Upper bound:} For each \(i\in[k-1]\), let \(T_i\) be the \(a-1\) smallest elements of \(D_i\), corresponding to the red rectangles in \cref{fig3}. We remove all relations between elements from \(T_i\) and elements from \(P_{1+k(m-1),S(k,m)}^\pi\setminus T_i\) for all $i$, to form a new poset \(U_{k}^\pi\) with at least \(r_{1+k(m-1),S(k,m)}^\pi\) linear extensions. As an example, the Hasse diagram of \(U^{\pi}_{4}\) is given on the left of \cref{fig4}.

\begin{figure}[htb]
\centering
%k=3
\begin{tikzpicture}[scale=.4]
    \draw [thick] (0,2) -- (0,4.25);
    \draw [thick] (0,6.25)--(0,8.75);
    \draw [thick] (0,10.75) -- (0,14);
    \draw[black,fill=black] (0,3) circle (.7ex);
    \draw[black,fill=black] (0,7.5) circle (.7ex);
    \draw[black,fill=black] (0,12) circle (.7ex);



    \draw [thick] (-1,4) -- (0,3);
    \draw [thick] (-1,8.5) -- (0,7.5);
    \draw [thick] (-1,13) -- (0,12);
%rotate around={45:(4,-1)}
    %lower arms
\draw[fill=red,shift={(3,0)} ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=red,shift={(6,0)}] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=red,shift={(9,0)} ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (3,2.8) {\(a-1\)};
\node at (6,2.8) {\(a-1\)};
\node at (9,2.8) {\(a-1\)};

    %upper arms
\draw[fill=blue,rotate around={225:(-1,4)},shift={(-1.25,1)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[fill=blue,rotate around={225:(-1,8.5)},shift={(-1.25,5.5)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[fill=blue,rotate around={225:(-1,13)},shift={(-1.25,10)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\node at (-4,5) {\(m-b\)};
\node at (-4,9.5) {\(m-b\)};
\node at (-4,14) {\(m-b\)};



%middle chain
\draw[fill=green,shift={(-.25,4.25)}, ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=green,shift={(-.25,8.75)}, ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (2.35,5) {\(b-a-1\)};
\node at (2.35,9.5) {\(b-a-1\)};

%top chain
\draw[fill=yellow,shift={(-.25,14)}, ] (0,0) -- (.5,0) -- (.5,4) -- (0,4) -- (0,0);
\node at (2,16) {\(m-a\)};

%bottom chain
\draw[fill=brown,shift={(-.25,-1.5)}, ] (0,0) -- (.5,0) -- (.5,3.5) -- (0,3.5) -- (0,0);
\node at (-2,0) {\(b-1\)};
\end{tikzpicture}\hspace{40pt}
\begin{tikzpicture}[scale=.4]
    \draw [thick] (0,3) -- (0,4.25);
    \draw [thick] (0,6.25)--(0,8.75);
    \draw [thick] (0,10.75) -- (0,14);
    \draw[black,fill=black] (0,3) circle (.7ex);
    \draw[black,fill=black] (0,7.5) circle (.7ex);
    \draw[black,fill=black] (0,12) circle (.7ex);

    \draw [thick] (-1,4) -- (0,3);
    \draw [thick] (-1,8.5) -- (0,7.5);
    \draw [thick] (-1,13) -- (0,12);
%rotate around={45:(4,-1)}
    %lower arms
\draw[fill=red,shift={(2,0)} ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=red,shift={(4,0)}] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=red,shift={(6,0)} ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (1.5,-0.75) {\(a-1\)};
\node at (4.25,-0.75) {\(a-1\)};
\node at (7,-0.75) {\(a-1\)};

    %upper arms
\draw[fill=blue,rotate around={225:(-1,4)},shift={(-1.25,1)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[fill=blue,rotate around={225:(-1,8.5)},shift={(-1.25,5.5)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\draw[fill=blue,rotate around={225:(-1,13)},shift={(-1.25,10)}, ] (0,0) -- (.5,0) -- (.5,3) -- (0,3) -- (0,0);
\node at (-4,5) {\(m-b\)};
\node at (-4,9.5) {\(m-b\)};
\node at (-4,14) {\(m-b\)};



%middle chain
\draw[fill=green,shift={(-.25,4.25)}, ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\draw[fill=green,shift={(-.25,8.75)}, ] (0,0) -- (.5,0) -- (.5,2) -- (0,2) -- (0,0);
\node at (2.35,5) {\(b-a-1\)};
\node at (2.35,9.5) {\(b-a-1\)};

%top chain
\draw[fill=yellow,shift={(-.25,14)}, ] (0,0) -- (.5,0) -- (.5,4) -- (0,4) -- (0,0);
\node at (2,16) {\(m-a\)};

%bottom chain
\draw[fill=brown,shift={(-.25,-1.5)}, ] (0,0) -- (.5,0) -- (.5,3.5) -- (0,3.5) -- (0,0);
\node at (-2,0) {\(b-1\)};


%connectives at the bottom
\draw [thick] (0,3) -- (0,2);
\draw [thick] (0,3) -- (2.25,2);
\draw [thick] (0,3) -- (4.25,2);
\draw [thick] (0,3) -- (6.25,2);

\end{tikzpicture}
\caption{The posets \(U_{4}^\pi\) (left) and \(L_4^\pi\) (right) of a permutation \(\pi\in\mfS_m\) in standard form with \(\pi_1=a\) and \(\pi_m=b\).}
\label{fig4}
\end{figure}

The number of linear extensions of \(U_k^\pi\) is 
\begin{align*}
u_k^\pi={1+k(m-1) \choose a-1,\dots a-1, 1+k(m-1)-(k-1)(a-1)}\prod_{i=1}^{k-1}{i(m-a)+m-b \choose m-b}=\chi_k^\pi\mu_k^\pi,
\end{align*}
where 
$$\chi_k^\pi=\frac{(1+k(m-1))!}{(a-1)!^{k-1}(a+k(m-a))!(m-b)!^{k-1}}$$ and $$\mu_k^\pi=\prod_{i=1}^{k-1}(i(m-a)+1)\cdots(i(m-a)+m-b).$$
As \(k\to\infty\), Stirling's formula gives \(\left(\chi_k^\pi\right)^{1/k}\sim\alpha k^{a-1}\),
where \(\alpha=\frac{(m-1)^{m-1}}{(a-1)!(m-b)!(m-a)^{m-a}e^{a-1}}\). 

We can bound $\mu_k^\pi$ as follows:
\[
(k-1)!^{m-b}(m-a)^{(m-b)(k-1)}=\prod_{i=1}^{k-1}(i(m-a))^{m-b}
\le \mu_k^\pi
\le k!^{m-b}(m-a)^{(m-b)(k-1)},
\]
where the last inequality uses the assumption that \(a<b\). Applying Stirling's formula again as
\(k\to\infty\), we obtain \(\left(\mu_k^\pi\right)^{1/k}\sim\beta k^{m-b}\),
where \(\beta=\frac{(m-a)^{m-b}}{e^{m-b}}\). Consequently \(\left(u_k^\pi\right)^{1/k}\sim\alpha\beta k^{m-b+a-1}\) as desired.

\noindent {\sl Lower bound:} Again we modify the relations between elements of \(T_i\) and the rest of the poset. This time we add relations to force every element in each \(T_i\) to be smaller than the \(b\)-th smallest element in \(L\). Let \(L_{k}^\pi\) be the resulting poset. As an example, the Hasse diagram of \(L^{\pi}_{4}\) is given on the right of \cref{fig4}.


The number of linear extensions \(L_k^\pi\) is 
$$\ell_k^\pi={b-1+(k-1)(a-1)\choose b-1,a-1,a-1,\ldots, a-1}\prod_{i=1}^{k-1}{i(m-a)+m-b \choose m-b}.$$
Again using Stirling's formula we see that, as \(k\to\infty\),
\[
\left(\ell_k^\pi\right)^{1/k}\sim \gamma k^{a-1} \beta k^{m-b}=\gamma\beta k^{m-b+a-1}
\]
where \(\gamma=\frac{(a-1)^{a-1}}{(a-1)!(m-b)!e^{a-1}}\).\end{proof}

\begin{proof}[Proof of \cref{thm2}]
Let \(\pi,\tau\in\mfS_m\) be in standard form. We prove the following stronger version of the contrapositive: if \(\pi_m-\pi_1<\tau_m-\tau_1\), then there is an integer \(K\) such that \(r_{1+k(m-1),k}^\tau<r_{1+k(m-1),k}^\pi\) for all \(k\ge K\). Indeed, since \(m-\tau_m+\tau_1-1<m-\pi_m+\pi_1-1\), we can take \(K\) such that
\(
U_\tau k^{m-\tau_m+\tau_1-1}<L_\pi k^{m-\pi_m+\pi_1-1}
\)
for all \(k\ge K\). Then, by \cref{lemma},
$$r_{1+k(m-1),k}^\tau\le\left(U_\tau k^{m-\tau_m+\tau_1-1}\right)^k<\left(L_\pi k^{m-\pi_m+\pi_1-1}\right)^k \le r_{1+k(m-1),k}^\pi$$
for all \(k\ge K\). In particular, by \cref{clustermethod}, $\pi$ and $\tau$ cannot be strongly c-Wilf equivalent.\end{proof}

\section{Super-strong c-Wilf equivalence}\label{superstrong}
We can use the refined cluster numbers to characterize super-strong c-Wilf equivalence in a similar way to how the cluster method (\cref{clustermethod}) characterizes strong c-Wilf equivalence in terms of regular cluster numbers. One difference, however, is that the refined version does not immediately lend itself to a generating function identity.

\begin{lem}
\label{lem:Cluster-ss}
Two permutations \(\pi,\tau\) are super-strongly c-Wilf equivalent if and only if \(r_{n,S}^\pi=r_{n,S}^\tau\) for all \(n\) and \(S\).
\end{lem}

\begin{proof} The forward direction is clear, since clusters are a particular kind of marked permutations. To prove the converse, let \(b_{n,S}^\pi\) be the number of \(\sigma\in\mfS_n\) with \(S\subseteq\Em(\pi,\sigma)\). By inclusion-exclusion, \(\pi,\tau\) are super-strongly c-Wilf equivalent if and only if \(b_{n,S}^\pi=b_{n,S}^\tau\) for all \(n\) and~\(S\), so it suffices to prove this equality.

Fix $\pi\in\mfS_m$, as well as $n$ and $S$. Consider a permutation \(\sigma\in\mfS_n\) chosen uniformly at random. We partition \(S=S_1\cup\dots\cup S_q\) for some \(q\ge1\), where each \(S_i\)  satisfies the following property: if \(x,y\in S\) with \(x<y\) and there is no \(z\in S\) with \(x<z<y\), then \(y-x\in\mcO_\pi\). Additionally, \(\max S_i+m-1<\min S_{i+1}\) for all \(i\in[q-1]\).
Letting \(m_i=\min S_i\) and \(M_i=\max S_i\), we claim that
\begin{align}
\label{eqn:probind}
\frac{b_{n,S}^\pi}{n!}=\prod_{i=1}^q \frac{r_{M_i-m_i+m,\widehat{S_i}}^\pi}{(M_i-m_i+m)!},
 \end{align}
 where \(\widehat{S_{i}}=\{i-m_i+1:i\in S_i\}\). To prove Equation~\eqref{eqn:probind}, let \(E_i\) be the event \(S_i\subseteq\Em(\pi,\sigma)\). Then the event \(E_1\cup\dots\cup E_q\) is equivalent to \(S\subseteq\Em(\pi,\sigma)\), and so it has probability \(b_{n,S}^\pi/n!\). By construction, the events \(E_i\) for $i\in[q]$ are mutually independent, and \(E_i\) occurs with probability \(\frac{r_{M_i-m_i+m,\widehat{S_i}}^\pi}{(M_i-m_i+m)!}\).

By hypothesis, the refined cluster numbers coincide for $\pi$ and $\tau$, and so the right hand side of Equation~\eqref{eqn:probind} stays the same when replacing $\pi$ with $\tau$. It follows that the the same holds for the left hand side, and so \(b_{n,S}^\pi=b_{n,S}^\tau\).\end{proof}
  
Using \cref{lem:Cluster-ss} and analyzing the cluster posets, one can derive the following generalization of \cref{thm:KS}. We omit the details due to space restrictions.
\begin{thm}\label{thm:DE-ss}
If \(\pi,\tau\in\mfS_m\) with \(\mcO_\pi=\mcO_\tau\) satisfy \(\{\pi_1,\dots,\pi_{m-i}\}=\{\tau_1,\dots,\tau_{m-i}\}\) and \(\{\pi_{i+1}\dots,\pi_m\}=\{\tau_{i+1},\dots,\tau_m\}\) for all \(i\in\mcO_\pi\), then $\pi$ and $\tau$ are super-strongly c-Wilf equivalent. 
\end{thm}

It is important to point out that \cref{conj:Nak} does not extend to super-strong c-Wilf equivalence, that is, there are permutations that are strongly c-Wilf equivalent but not super-strongly c-Wilf equivalent.
For example, we have computed that \(a_{9,\{3\}}^{1423}=13,843\neq 13,839=a_{9,\{3\}}^{3241}\), despite the fact that \(1423^R=3241\). 

However, we have proved that the three equivalence relations that we have defined do in fact coincide when restricted to non-overlapping permutations. We have two proofs of the following theorem. The first one uses techniques similar to those in Billey, Burdzy and Sagan's work on permutations with a given peak set~\cite{BBS2013}. The second uses \cref{lemma} and some ideas from~\cite{ElizaldeMostLeast2013}.
\begin{thm}\label{thm:eq-sseq}
Let \(\pi,\tau \in\mfS_m\) be non-overlapping permutations. If \(\pi\) and \(\tau\) are c-Wilf equivalent then they are super-strongly c-Wilf equivalent. 
\end{thm}

Since every permutation is c-Wilf equivalent to its reversal, an immediate consequence of \cref{thm:eq-sseq} is that if $\pi$ is non-overlapping, then $\pi$ and $\pi^R$ are super-strongly c-Wilf equivalent. It would be interesting to find a combinatorial proof of this fact, that is, a bijection from $\mfS_n$ to itself changing occurrences of $\pi$ in prescribed positions into occurrences of $\pi^R$. This is challenging even in simplest case of $\pi=132$.



\printbibliography

\end{document}

